import java.util.Arrays;

public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] buck;       //桶数组
    public int usedSize;      //桶的实际个数
    double load_factor=0.75f; //负载因子

    public HashBuck() {
        this.buck = new Node[10];
    }

    public void put(int key,int val){
        int index=key%buck.length;
        Node cur=buck[index];

        //遍历寻找键值对插入的位置
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
                return ;
            }
            cur=cur.next;
        }

        //进行头插(实际实现为尾插，这里写成头插是为了方便演示)
        Node newNode=new Node(key,val);
        newNode.next=buck[index];
        usedSize++;

        if(usedSize*1.0/ buck.length>load_factor){
            //如果超过负载因此，则需要扩容
            grow();
        }
    }

    //扩容
    private void grow(){
        //面试题：重新哈希(扩容时)，需要注意什么？
        //     =>将原本哈希表的元素进行重新映射
        Node[] newBuck=new Node[2*buck.length];

        for(int i=0;i<usedSize;i++){
            //拿到第i个桶
            Node cur=buck[i];
            //将桶的每个元素均进行映射到新的位置
            while(cur!=null){
                //保持下一个元素，以防止映射后位置丢失
                Node nextNode=cur.next;
                //头插
                int index=cur.key% newBuck.length;
                cur.next=newBuck[index];
                newBuck[index]=cur;
                cur=nextNode;
            }
        }
        this.buck=newBuck;
    }

    //根据key拿到对应的val
    public int get(int key){
        int index=key%buck.length;
        Node cur=buck[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }
}
